package com.xiaoyg.algorithm;

import java.util.HashMap;
import java.util.Map;

public class ClimbStairs {

    public static void main(String[] args) {
        System.out.println("climb3: " + climbStairs3(3));
        System.out.println("climb4: " + climbStairs3(4));
    }


    public static int climbStairs1(int n){
        //递归终止条件
        if(n == 1) return 1;
        if(n == 2) return 2;
        //递归条件
        return climbStairs1(n - 1) + climbStairs1(n - 2);
    }

    public static int climbStairs2(int n){
        //添加备忘录存储已经计算的值
        Map<Integer, Integer> map = new HashMap<>();
        //备忘录的递归
        if(n == 1) return 1;
        if(n == 2) return 2;
        //取出已经计算的值
        if (null != map.get(n)){
            return map.get(n);
        }
        //计算结果值
        int result = climbStairs2(n - 1) +climbStairs2(n - 2);
        map.put(n, result);
        return result;
    }


    public static int climbStairs3(int n){
        if(n == 1) return 1;
        if(n == 2) return 2;
        int pre = 2;
        int prePre = 1;
        for (int i = 3;i<=n;i++){
            int temp = pre;
            pre = pre + prePre;
            prePre = temp;
        }
        return pre;
    }


}
